package com.desheng.bigdata.ds.link;

/**
 * @Description 单向链表
 * @Author deshenglijun
 * @Date 2020/5/10 19:35
 * @Version 1.0
 */
public class OneWayLinkedList<E> {

    private Node<E> head;//头节点
    private int size;

    class Node<E> {
        E data;//当前节点数据
        Node<E> next;//后继节点

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    //将指定元素添加到此列表的结尾。
    public boolean add(E e) {
        if(this.head == null) {
            this.head = new Node<>(e, null);
        } else {
            //获取最后一个节点
            Node<E> lastNode = getLastNode();
            //给最后一个节点添加新的节点
            lastNode.next = new Node(e, null);
            //size加1
        }
        size++;
        return true;
    }
    //将指定元素插入此列表的开头。
    public void addFirst(E e) {
        if(this.head == null) {
            this.head = new Node<>(e, null);
        } else {
            Node<E> node = this.head;
            this.head = new Node<>(e, node);
        }
        size++;
    }

    /**
     * 在此列表中指定的位置插入指定的元素。
     * 思路：关键在于如何定位到索引对应的节点
     */
    public void add(int index, E element) {
        checkIndex(index);
        Node<E> curNode = this.head;
        if(index == 0) {
            this.head = new Node<>(element, curNode);
        } else {
            for(int i = 0; i < index - 1; i++) {
                curNode = curNode.next;
            }
            Node nextNode = curNode.next;
            curNode.next = new Node(element, nextNode);
        }
        size++;
    }

    /**
     添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
     *  被添加的链表bMll(bHead, bTail)
     *  添加的链表mll(head, tail)
     *  head -->node ->bHead-->bTail(tail)
     */
    public boolean addAll(OneWayLinkedList<E> owl) {
        if(owl == null || owl.size < 1) {
            return false;
        }
        if(this.head == null) {
            this.head = owl.head;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = owl.head;
        }
        size += owl.size;
        return true;
    }

    /**
     * 获取单向链表中的最后一个元素
     * @return
     */
    private Node<E> getLastNode() {
        Node<E> node = this.head;
        while(node.next != null) {
            node = node.next;
        }
        return node;
    }
    /**
     添加指定 collection 中的所有元素到此列表的指定位置。
     *  被添加的链表bMll(bHead, bTail)
     *  添加的链表mll(head, tail)
     *  head -->currNode ->bHead-->bTail -->nextNode-->tail
     */
    public boolean addAll(int index, OneWayLinkedList<E> owl) {
        if(owl == null || owl.size < 1) {
            return false;
        }
        if(index == 0) {
            owl.addAll(this);
            this.head = owl.head;
            this.size = owl.size;
        } else {
            Node<E> currNode = getNodeByIndex(index - 1);
            Node nextNode = currNode.next;
            Node<E> lastNode1 = owl.getLastNode();
            currNode.next = owl.head;
            lastNode1.next = nextNode;
            size += owl.size;
        }
        return true;
    }


    //    如果此列表包含指定元素，则返回 true。
    public boolean contains(Object o) {
        return indexOf(o) != -1 ? true : false;
    }
    //返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
    public int indexOf(Object o) {
        Node<E> node = this.head;
        for(int i = 0; i < size; i++) {
            if(node.data.equals(o)) {
                return i;
            }
            node = node.next;
        }
        return -1;
    }

    //移除此列表中指定位置处的元素。
    public E remove(int index) {
        if(index == 0) {
            return removeFirst();
        }
        Node<E> node = getNodeByIndex(index - 1);
        E oldValue = node.next.data;
        node.next = node.next.next;
        size--;
        return oldValue;
    }

    //从此列表中移除首次出现的指定元素（如果存在）。-->从前往后找
    public boolean remove(Object o) {
        int index = indexOf(o);
        E remove = remove(index);
        return remove != null;
    }


    //移除并返回此列表的第一个元素。
    public E removeFirst() {
        if(this.head != null) {
            Node<E> node = this.head;
            this.head = node.next;
            size--;
            return node.data;
        }
        return null;
    }
    //移除并返回此列表的最后一个元素。
    public E removeLast() {
        E oldValue = null;
        if(size <= 1) {
            oldValue = this.head.data;
            this.head = null;
        } else {
            Node<E> node = getNodeByIndex(size - 2);
            oldValue = node.next.data;
            node.next = null;
        }
        size--;
        return oldValue;
    }
    public boolean isEmpty() {
        return size == 0;
    }

    //    将此列表中指定位置的元素替换为指定的元素。
    public E set(int index, E element) {
        Node<E> node = getNodeByIndex(index);
        E oldValue = node.data;
        node.data = element;
        return oldValue;
    }
    ///////////////////////////

    //从此列表中移除所有元素。
    public void clear() {
        this.size = 0;
        head = null;
    }

    //返回此列表的第一个元素。
    public E getFirst() {
        return head == null ? null : head.data;
    }

    public int size() {
        return this.size;
    }

    //返回此列表中指定位置处的元素。
    public E get(int index) {
        return getNodeByIndex(index).data;
    }

    /**
     * 获取指定索引位置的元素
     * @param index
     * @return
     */
    private Node<E> getNodeByIndex(int index) {
        checkIndex(index);
        Node<E> node = this.head;
        for(int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if(head != null) {//放置空链表而造成的空指针问题
            Node node = head;
            while (node.next != null) {
                sb.append(node.data).append(", ");
                node = node.next;
            }
            //到这里说明什么问题 最后一个元素没有进行提取(最后一个元素就是node)
            if (node != null) {
                sb.append(node.data);
            }
        }
        sb.append("]");

        return sb.toString();
    }

    private void checkIndex(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
    }

    /**
     * 链表反转
     * 1->2->3->4
     * ==>
     * 4->3->2->1
     */
    public void reverse() {
        if(isEmpty()) {
            return;
        }
        this.head = reverse(this.head);
    }

    private Node<E> reverse(Node<E> node) {
        Node<E> pre = null;//前驱节点
        while(node != null) {
            Node<E> tmp = node.next; //临时节点
            node.next = pre;
            pre = node;
            node = tmp;
        }
        return pre;
    }
}
